package lib

import (
	"algorithms/ds"
	"math"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         98,
		Discription: "验证二叉搜索树",
		Level:       2,
		Labels: map[string]int{
			"递归":    1,
			"二叉树":   1,
			"二叉搜索树": 1,
		},
	})
}

func IsValidBST(root *ds.TreeNode) bool {
	//维护上下界即可
	var isValid func(*ds.TreeNode, int, int) bool
	isValid = func(node *ds.TreeNode, min int, max int) bool {
		if node == nil {
			return true
		}

		if node.Val <= min || node.Val >= max {
			return false
		}

		return isValid(node.Left, min, node.Val) && isValid(node.Right, node.Val, max)
	}

	//必须是int64，因为题目的范围里有int32的最大值
	return isValid(root, math.MinInt64, math.MaxInt64)
}
